from copy import deepcopy


def win_lose_judge(chess_state, color):
    if color == "white":
        color_mark = 1
    else:
        color_mark = 2

    for i in range(0, 15):
        for j in range(0, 15):
            if chess_state[i][j] == color_mark:
                if single_win_check(chess_state, [i, j]):
                    if color_mark == 1:
                        return "white"
                    if color_mark == 2:
                        return "black"

    return "no"


def single_win_check(chess_state, pos):
    possible_directions = []
    if pos[1] >= 4:
        possible_directions.append([0, -1])
    if pos[1] >= 4 and pos[0] <= 10:
        possible_directions.append([1, -1])
    if pos[0] <= 10:
        possible_directions.append([1, 0])
    if pos[0] <= 10 and pos[1] <= 10:
        possible_directions.append([1, 1])
    if pos[1] <= 10:
        possible_directions.append([0, 1])
    if pos[0] >= 4 and pos[1] <= 10:
        possible_directions.append([-1, 1])
    if pos[0] >= 4:
        possible_directions.append([-1, 0])
    if pos[0] >= 4 and pos[1] >= 4:
        possible_directions.append([-1, -1])
    for direct in possible_directions:
        if single_direction_win(chess_state, pos, direct):
            return True
    return False


def single_direction_win(chess_state, pos, direction):
    x = direction[0]
    y = direction[1]
    return chess_state[pos[0]][pos[1]] == chess_state[pos[0] + x][pos[1] + y] and \
        chess_state[pos[0] + x][pos[1] + y] == chess_state[pos[0] + 2 * x][pos[1] + 2 * y] and \
        chess_state[pos[0] + 2 * x][pos[1] + 2 * y] == chess_state[pos[0] + 3 * x][pos[1] + 3 * y] and \
        chess_state[pos[0] + 3 * x][pos[1] + 3 * y] == chess_state[pos[0] + 4 * x][pos[1] + 4 * y]


class Node:
    def __init__(self, depth, father, board):
        self.depth = depth
        self.value = 0
        self.father = father
        self.children = []
        self.board = deepcopy(board)
        self.has_won = self.board_identify()

    def is_max_node(self):
        if self.depth % 2 == 0:
            return True
        else:
            return False

    def node_evaluate(self):
        if self.is_max_node() and self.has_won == "white":
            self.value = 100000000
        elif self.is_max_node() and self.has_won == "no":
            self.value = evaluate(self.board, "black") - evaluate(self.board, "white")
        elif (not self.is_max_node()) and self.has_won == "black":
            self.value = 10000000
        else:
            self.value = evaluate(self.board, "black") - evaluate(self.board, "white")

    def board_identify(self):
        # 放白后得到最大节点，所以在最大节点看白是否胜利，最小节点看黑是否胜利
        if self.is_max_node():
            return win_lose_judge(self.board, "white")
        else:
            return win_lose_judge(self.board, "black")


class GameTree:
    def __init__(self, radius, max_depth, root_node, now_board):
        self.radius = radius
        self.max_depth = max_depth
        self.root_node = root_node
        self.next_node = None
        self.non_expand_nodes = []
        self.expanded_nodes = []
        self.now_board = deepcopy(now_board)

    def set_next_pos(self):
        if len(self.root_node.children) > 0:
            next_node = self.root_node.children[0]
            for n in self.root_node.children:
                if n.value > next_node.value:
                    next_node = n
            return deepcopy(next_node.board)
        else:
            return None

    def game(self):
        # 博弈控制函数，返回下一步棋的位置
        self.non_expand_nodes.append(self.root_node)
        while not len(self.non_expand_nodes) == 0:
            node = self.non_expand_nodes[0]
            self.expanded_nodes.append(node)
            del(self.non_expand_nodes[0])
            if self.is_alpha_beta_cut(node.father):
                continue
            if node.depth < self.max_depth and node.has_won == "no":  # 此处保证已经有胜负的棋局不会被扩展
                self.expand_children_nodes(node)
                if len(node.children) > 0:
                    continue
            node.node_evaluate()
            self.update_value_from_node(node)
        next_step_board = self.set_next_pos()
        if next_step_board is not None:
            for i in range(0, 15):
                for j in range(0, 15):
                    if self.now_board[i][j] == 0 and next_step_board[i][j] == 2:
                        return [i, j]
        else:
            return None

    def is_alpha_beta_cut(self, node):
        if node is None or node.father is None:
            return False
        else:
            if node.is_max_node() and node.value > node.father.value:
                return True
            if (not node.is_max_node()) and node.value < node.father.value:
                return True
            return self.is_alpha_beta_cut(node.father)

    def expand_children_nodes(self, node):
        new_positions = self.search_nodes(node)
        for position in new_positions:
            possible_chess_state = deepcopy(node.board)
            if node.depth % 2 == 0:
                possible_chess_state[position[0]][position[1]] = 2
            else:
                possible_chess_state[position[0]][position[1]] = 1
            new_node = Node(node.depth + 1, node, deepcopy(possible_chess_state))
            node.children.append(new_node)
            self.non_expand_nodes.insert(0, new_node)
        return

    def update_value_from_node(self, node):
        if node is None or node.father is None:
            return
        if len(node.children) == 0:
            self.update_value_from_node(node.father)
        else:
            if node.is_max_node():
                largest_value = max([child_node.value for child_node in node.children])
                if largest_value > node.value:
                    node.value = largest_value
                    self.update_value_from_node(node.father)
            if not node.is_max_node():
                smallest_value = min([child_node.value for child_node in node.children])
                if smallest_value < node.value:
                    node.value = smallest_value
                    self.update_value_from_node(node.father)
        return

    def search_nodes(self, node):
        # 0 为没有棋子，1为本来就有棋子，2为新棋子的位置
        chess_judge = [[0 for i in range(0, 15)] for j in range(0, 15)]
        new_positions = []
        for i in range(0, 15):
            for j in range(0, 15):
                if not node.board[i][j] == 0:
                    chess_judge[i][j] = 1
        for i in range(0, 15):
            for j in range(0, 15):
                if chess_judge[i][j] == 0:  # 如果这个位置没有棋子
                    for m in range(max([i - self.radius, 0]), min([i + self.radius + 1, 15])):
                        for n in range(max([j - self.radius, 0]), min([j + self.radius + 1, 15])):
                            if chess_judge[m][n] == 1:  # 如果这个位置半径范围内有棋子
                                new_positions.append([i, j])
                                chess_judge[i][j] = 2
        return new_positions


def evaluate(chess_state, color):
    if color == "white":
        color_mark = 1
    else:
        color_mark = 2

    count5 = 0
    count_single4 = 0
    count_double3 = 0
    count_single3 = 0
    count_single2 = 0
    rate_5 = 100000
    rate_single4 = 10000
    rate_double3 = 1000
    rate_single3 = 100
    rate_single2 = 10

    # 对 5 和 4两头有空 计数
    # 5个都在一条直线上，4两头有空，也需要5的空间，所以范围缩小到4~10即可
    for i in range(4, 11):
        for j in range(4, 11):
            if chess_state[i][j] == color_mark:
                possible_directions = [[0, -1], [1, -1], [1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1]]
                for direct in possible_directions:
                    x = direct[0]
                    y = direct[1]
                    # 对5连计数
                    if chess_state[i][j] == chess_state[i + x][j + y] and \
                            chess_state[i + x][j + y] == chess_state[i + 2 * x][j + 2 * y] and \
                            chess_state[i + 2 * x][j + 2 * y] == chess_state[i + 3 * x][j + 3 * y] and \
                            chess_state[i + 3 * x][j + 3 * y] == chess_state[i + 4 * x][j + 4 * y]:
                        count5 += 1
                    # 对4两头空计数
                    if chess_state[i][j] == chess_state[i + x][j + y] and \
                            chess_state[i + x][j + y] == chess_state[i + 2 * x][j + 2 * y] and \
                            chess_state[i + 2 * x][j + 2 * y] == chess_state[i + 3 * x][j + 3 * y] and \
                            chess_state[i + 4 * x][j + 4 * y] == 0 and chess_state[i - x][j - y] == 0:
                        count_single4 += 1

    # 双三的匹配对于边界有些问题，不过不影响测试估值函数的合理性
    # 对双三计数，先考虑两个三共用一个角
    for i in range(1, 14):
        for j in range(1, 14):
            if chess_state[i][j] == color_mark:
                possible_directions = []
                if j >= 3:
                    possible_directions.append([0, -1])
                if j >= 3 and i <= 11:
                    possible_directions.append([1, -1])
                if i <= 11:
                    possible_directions.append([1, 0])
                if i <= 11 and j <= 11:
                    possible_directions.append([1, 1])
                if j <= 11:
                    possible_directions.append([0, 1])
                if i >= 3 and j <= 11:
                    possible_directions.append([-1, 1])
                if i >= 3:
                    possible_directions.append([-1, 0])
                if i >= 3 and j >= 3:
                    possible_directions.append([-1, -1])
                # 方向成对进行检测
                if len(possible_directions) > 1:
                    direction_pairs = []
                    for index in range(0, len(possible_directions) - 1):
                        for index_2 in range(index + 1, len(possible_directions)):
                            direction_pairs.append([possible_directions[index], possible_directions[index_2]])
                    for pair in direction_pairs:
                        x1, y1, x2, y2 = pair[0][0], pair[0][1], pair[1][0], pair[1][1]
                        if chess_state[i][j] == chess_state[i + x1][j + y1] and \
                                chess_state[i + x1][j + y1] == chess_state[i + 2 * x1][j + 2 * y1] and \
                                chess_state[i + 3 * x1][j + 3 * y1] == 0 and \
                                chess_state[i - x1][j - y1] == 0 and \
                                chess_state[i][j] == chess_state[i + x2][j + y2] and \
                                chess_state[i + x2][j + y2] == chess_state[i + 2 * x2][j + 2 * y2] and \
                                chess_state[i + 3 * x2][j + 3 * y2] == 0 and \
                                chess_state[i - x2][j - y2] == 0:
                            count_double3 += 1

    # 双三只有一个在中间的情况和两个在中间的情况，这里对于边界的匹配不好，不过不影响判断估值函数的合理性
    for i in range(3, 12):
        for j in range(3, 12):
            if chess_state[i][j] == color_mark:
                possible_directions = [[0, -1], [1, -1], [1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1]]
                # 方向成对进行检测
                direction_pairs = []
                for index in range(0, len(possible_directions) - 1):
                    for index_2 in range(index + 1, len(possible_directions)):
                        direction_pairs.append(
                            [possible_directions[index], possible_directions[index_2]])
                for pair in direction_pairs:
                    x1, y1, x2, y2 = pair[0][0], pair[0][1], pair[1][0], pair[1][1]
                    if chess_state[i][j] == chess_state[i + x1][j + y1] and \
                            chess_state[i + x1][j + y1] == chess_state[i + 2 * x1][j + 2 * y1] and \
                            chess_state[i + 3 * x1][j + 3 * y1] == 0 and \
                            chess_state[i - x1][j - y1] == 0 and \
                            chess_state[i][j] == chess_state[i + x2][j + y2] and \
                            chess_state[i + x2][j + y2] == chess_state[i - x2][j - y2] and \
                            chess_state[i + 2 * x2][j + 2 * y2] == 0 and \
                            chess_state[i - 2 * x2][j - 2 * y2] == 0:
                        count_double3 += 1

                    if chess_state[i][j] == chess_state[i + x1][j + y1] and \
                            chess_state[i + x1][j + y1] == chess_state[i - x1][j - y1] and \
                            chess_state[i + 2 * x1][j + 2 * y1] == 0 and \
                            chess_state[i - 2 * x1][j - 2 * y1] == 0 and \
                            chess_state[i][j] == chess_state[i + x2][j + y2] and \
                            chess_state[i + x2][j + y2] == chess_state[i - x2][j - y2] and \
                            chess_state[i + 2 * x2][j + 2 * y2] == 0 and \
                            chess_state[i - 2 * x2][j - 2 * y2] == 0:
                        count_double3 += 1

                # 对3两头空计数
                for direct in possible_directions:
                    x, y = direct[0], direct[1]
                    if chess_state[i][j] == chess_state[i + x][j + y] and \
                            chess_state[i + x][j + y] == chess_state[i + 2 * x][j + 2 * y] and \
                            chess_state[i + 3 * x][j + 3 * y] == 0 and chess_state[i - x][j - y] == 0:
                        count_single3 += 1

    # 对2两头空计数
    for i in range(2, 13):
        for j in range(2, 13):
            if chess_state[i][j] == color_mark:
                possible_directions = [[0, -1], [1, -1], [1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1]]
                for direct in possible_directions:
                    x, y = direct[0], direct[1]
                    if chess_state[i][j] == chess_state[i + x][j + y] and \
                            chess_state[i + 2 * x][j + 2 * y] == 0 and chess_state[i - x][j - y] == 0:
                        count_single2 += 1

    return count5 * rate_5 + count_single4 * rate_single4 + count_double3 * rate_double3 + count_single3 * rate_single3 + count_single2 * rate_single2


def game_logic(chess_state):
    max_depth = 1
    radius = 1
    root_node = Node(0, None, chess_state)
    game_tree = GameTree(radius, max_depth, root_node, chess_state)
    return game_tree.game()